package com.zzh.arithmetic.demo;

import com.zzh.arithmetic.model.ListNode;

/**
 * @author zihong.zheng
 * @version 1.0
 * @date 2021/4/17
 * @time 19:11
 * @description 链表反转算法 有两种算法
 * 效果如下：
 * 1->2->3->4->NULL
 * 4->3->2->1->NULL
 */
public class ListNodeReverseDemo {

    public static void main(String[] args) {
        ListNode listNode0 = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(11);
        ListNode listNode5 = new ListNode(12);
        listNode0.setNext(listNode1);
        listNode1.setNext(listNode2);
        listNode2.setNext(listNode3);
        listNode3.setNext(listNode4);
        listNode4.setNext(listNode5);
        ListNode listNode = ListNodeReverseDemo.reverse1(listNode0);
        while (listNode != null) {
            System.out.println(listNode.getVal());
            listNode = listNode.getNext();
        }
    }


    /**
     * 循环步骤如下preNode节点变化如下
     *  1->null
     *  2->1->null
     *  3->2->1->null
     *  4->3->2->1->null
     *  11->4->3->2->1->null
     *  12->11->4->3->2->1->null
     *
     * @param head
     * @return
     */
    public static ListNode reverse1(ListNode head) {

        //设置三个节点，当前节点，上个节点，以及下个节点，将当前节点设置为头节点
        ListNode currentNode = head;
        ListNode preNode = null;
        ListNode nextNode;
        //while循环，条件当前节点不会空，
        while (currentNode != null) {
            nextNode = currentNode.getNext();
            currentNode.setNext(preNode);
            preNode = currentNode;
            currentNode = nextNode;
        }
        return preNode;
    }


    /**
     * 1->2->3->4->NULL
     * 4->3->2->1->NULL
     *
     * @param head
     * @return
     */
    public static ListNode reverse2(ListNode head) {
        if (head == null || head.getNext() == null) {
            return head;
        }
        //递归当前节点的下个节点 目的找到最后一个节点
        ListNode p = reverse2(head.getNext());
        //反转节点
        //获取到当前节点的下个节点设置它的下个节点为当前节点
        head.getNext().setNext(head);
        //切断当前节点与下个节点关联
        head.setNext(null);
        //每次返回的都是尾节点也就是新的链表头
        return p;
    }


}
